/*-
 * Copyright (c) 2006, 2007 FTS Team
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 4. Neither the name of the FTS Team nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *      Hash.hpp
 *
 * $FTS$
 */
#ifndef _HASH_HPP__
#define _HASH_HPP__ 1

/**
  @file Hash.hpp
  @brief Generic hash class
*/
#include <Allocator.hpp>
#include <FTSTypes.h>
#include <Pair.hpp>

namespace FTSS // FullTextSearchSystem
{
#ifndef WIN32
#define C_USED_CELL     0x8000000000000000llu
#define C_ERASED_CELL   0x4000000000000000llu
#define C_MAX_HASH_MASK 0x3FFFFFFFFFFFFFFFllu
#else
#define C_USED_CELL     0x8000000000000000ll
#define C_ERASED_CELL   0x4000000000000000ll
#define C_MAX_HASH_MASK 0x3FFFFFFFFFFFFFFFll
#endif // WIN32

/**
  @class HashTable Hash.hpp <Hash.hpp>
  @brief Hash table
*/
template <typename TKey, typename TVal> struct HashTable
{
	/** Hash                */
	TokenHash_t        hash;
	/** Stored data         */
	Pair<TKey, TVal>   data;
	/** Default constructor */
	inline HashTable(): hash(0), data(Pair<TKey, TVal>()) { ;; }
};

/**
  @class HashStorage Hash.hpp <Hash.hpp>
  @brief Hash storage
*/
template <typename TKey, typename TVal> struct HashStorage
{
	/** Maximum hash size      */
	UINT_64                  max_size;
	/** Used elements          */
	UINT_64                  used;
	/** Hash bitmask           */
	UINT_64                  bit_mask;
	/** Reference Count        */
	UINT_64                  refcount;
	/** hash table             */
	HashTable<TKey, TVal> * hash_table;

	/** Default constructor */
	inline HashStorage(): max_size(0), used(0), bit_mask(0), refcount(1), hash_table(NULL) { ;; }
};

/**
  @class Hash Hash.hpp <Hash.hpp>
  @brief Generic hash
*/
template <typename TKey,
          typename TVal,
          typename THashFN,
          typename TCmpFN,
          typename AllocTable = Allocator<HashTable<TKey, TVal> >,
          typename AllocStor  = Allocator<HashStorage<TKey, TVal> > >class Hash
{
protected:
	/** Allocator for table               */
	AllocTable   oTableAllocator;
	/** Allocator for hash shared storage */
	AllocStor    oStorageAllocator;
	/** Hasher                            */
	THashFN         oHashFun;
	/** Comparator                        */
	TCmpFN          oCmpFun;
	/** Hash data stroage                 */
	HashStorage<TKey, TVal>   * pStorage;
public:

	/**
	  @brief Default constructor
	  @param iHashSize - initial hash size, default 2
	  @param oITableAllocator - default memory allocator for stored data
	  @param oIStorageAllocator - default memory allocator for hash internal data
	*/
	Hash(UINT_64 iHashSize = 2, AllocTable oITableAllocator = AllocTable(), AllocStor oIStorageAllocator = AllocStor());

	/**
	  @brief Copy constructor
	  @param oRhs - object to copy
	*/
	inline Hash(const Hash<TKey, TVal, THashFN, TCmpFN, AllocTable, AllocStor> & oRhs): oTableAllocator(oRhs.oTableAllocator),
	                                                                             oStorageAllocator(oRhs.oStorageAllocator),
	                                                                             oHashFun(oRhs.oHashFun),
	                                                                             oCmpFun(oRhs.oCmpFun),
	                                                                             pStorage(oRhs.pStorage)
	{
		++ pStorage -> refcount;
	}

	/**
	  @brief Assignment operator
	  @param oRhs - object to copy
	*/
	inline Hash<TKey, TVal, THashFN, TCmpFN, AllocTable, AllocStor> & operator=(const Hash<TKey, TVal, THashFN, TCmpFN, AllocTable, AllocStor> & oRhs)
	{
		if (this != &oRhs)
		{
			Destroy();
			oTableAllocator   = oRhs.oTableAllocator;
			oStorageAllocator = oRhs.oIStorageAllocator;
			oHashFun          = oRhs.oHashFun;
			oCmpFun           = oRhs.oCmpFun;
			pStorage          = oRhs.pStorage;
			++ pStorage -> refcount;
		}
	return *this;
	}

	/**
	  @brief A destructor
	*/
	~Hash() throw()
	{
		Destroy();
	}

	/**
	  @class base_iterator Hash.hpp <Hash.hpp>
	  @brief Hash forward iterator
	*/
	template <typename TKeyIt, typename TValIt> class base_iterator
	{
	public:
		/**
		  @brief Constructor
		*/
		base_iterator(const UINT_64 iIPos = 0, HashStorage<TKey, TVal> * pIStorage = NULL): iPos(iIPos), pStorage(pIStorage)
		{
			while(iPos != pStorage -> max_size && !(pStorage -> hash_table[iPos].hash & C_USED_CELL)) { ++iPos; }
		}

		/**
		  @brief Copy constructor
		  @param oRhs - object to copy
		*/
		base_iterator(const base_iterator<TKeyIt, TValIt> & oRhs)
		{
			pStorage = oRhs.pStorage;
			iPos     = oRhs.iPos;
		}

		/**
		  @brief Assignment operator
		  @param oRhs - object to copy
		*/
		inline base_iterator<TKeyIt, TValIt> & operator=(const base_iterator<TKeyIt, TValIt> & oRhs)
		{
			pStorage = oRhs.pStorage;
			iPos     = oRhs.iPos;
			return *this;
		}

		/**
		  @brief Prefix operator ++
		*/
		inline base_iterator<TKeyIt, TValIt> operator++()
		{
			if (iPos == pStorage -> max_size) { return *this; }
			iPos++;
			for(;;)
			{
				if (iPos == pStorage -> max_size) { break; }
				if (pStorage -> hash_table[iPos].hash & C_USED_CELL) { break; }
				iPos++;
			}
			return *this;
		}

		/**
		  @brief Postfix operator ++
		*/
		base_iterator<TKeyIt, TValIt> operator++(int)
		{
			if (iPos == pStorage -> max_size) { return *this; }
			base_iterator<TKeyIt, TValIt> oTMP(*this);
			iPos++;
			for(;;)
			{
				if (iPos == pStorage -> max_size) { break; }
				if (pStorage -> hash_table[iPos].hash & C_USED_CELL) { break; }
				iPos++;
			}
			return oTMP;
		}

		/**
		  @brief Pointer operator ->
		*/
		inline Pair<TKeyIt, TValIt> * operator->() { return &(pStorage -> hash_table[iPos].data); }

		/**
		  @brief Reference operator *
		*/
		inline Pair<TKeyIt, TValIt> & operator*() { return pStorage -> hash_table[iPos].data; }

		/**
		  @brief operator ==
		  @param oRhs - object to compare
		  @return true if iterators are equal
		*/
		inline bool operator==(const base_iterator<TKeyIt, TValIt> & oRhs) const { return ((pStorage == oRhs.pStorage) && (iPos == oRhs.iPos)); }

		/**
		  @brief operator !=
		  @param oRhs - object to compare
		  @return true if iterators are NOT equal
		*/
		inline bool operator!=(const base_iterator<TKeyIt, TValIt> & oRhs) const { return (!((pStorage == oRhs.pStorage) && (iPos == oRhs.iPos))); }

	private:
		/** Iterator position */
		UINT_64                     iPos;
		/** Data storage      */
		HashStorage<TKey, TVal>   * pStorage;
	};

	/**
	  @typedef typedef base_iterator<TKey, TVal> iterator
	  @brief Forward iterator declaration
	*/
	typedef base_iterator<TKey, TVal>                   iterator;

	/**
	  @typedef base_iterator<const TKey, const TVal> const_iterator
	  @brief Forward constant iterator declaration
	*/
	typedef base_iterator<const TKey, const TVal> const_iterator;

	/**
	  @brief Get iterator that points to the first element in the hash
	  @return Returns a read/write iterator that points to the first element in the hash.
	*/
	inline iterator begin() { return iterator(0, pStorage); }

	/**
	  @brief Get iterator that points one past the last element in the hash
	  @return Returns a read/write iterator that points one past the last element in the hash.
	*/
	inline iterator end()   { return iterator(pStorage -> max_size, pStorage); }

	/**
	  @brief Get read-only iterator that points to the first element in the hash
	  @return Returns a read/write iterator that points to the first element in the hash.
	*/
	inline const_iterator begin() const { return iterator(0, pStorage); }

	/**
	  @brief Get read-only iterator that points one past the last element in the hash
	  @return Returns a read/write iterator that points one past the last element in the hash.
	*/
	inline const_iterator end()   const { return iterator(pStorage -> max_size, pStorage); }

	/**
	  @brief Insert element into hash
	  @param oPair - Pair of (key, value) to insert
	  @return 0 if success, -1 if error occures and 1 if duplicate found
	*/
	inline INT_32 insert(const Pair<TKey, TVal> & oPair)
	{
		TokenHash_t iHash = oHashFun(oPair.first) & C_MAX_HASH_MASK;

	return insert(oPair, iHash);
	}

	/**
	  @brief Insert element into hash
	  @param oPair - Pair of (key, value) to insert
	  @param iHash - key hash
	  @return 0 if success, -1 if error occures and 1 if duplicate found
	*/
	INT_32 insert(const Pair<TKey, TVal> & oPair, TokenHash_t iHash);

	/**
	  @brief Remove element from hash
	  @param oKey - key to remove
	  @return 0 if sucess, -1 if key not found
	*/
	inline INT_32 erase(const TKey & oKey)
	{
		TokenHash_t iHash = oHashFun(oKey) & C_MAX_HASH_MASK;

	return erase(oKey, iHash);
	}

	/**
	  @brief Remove element from hash
	  @param oKey - key to remove
	  @param iHash - key hash
	  @return 0 if sucess, -1 if key not found
	*/
	INT_32 erase(const TKey & oKey, TokenHash_t iHash);

	/**
	  @brief Get hash size
	  @return Current mulber of elements in hash
	*/
	inline UINT_64 size() { return pStorage -> used; }

	/**
	  @brief Get hash capacity
	  @return Current hash capacity in elements
	*/
	inline UINT_64 capacity() { return pStorage -> max_size; }

	/**
	  @brief Find element in hash
	  @param oKey - key to find
	  @return Iterator, piointed to element of end() if key not found
	*/
	inline iterator find(const TKey & oKey)
	{
		TokenHash_t iHash = oHashFun(oKey) & C_MAX_HASH_MASK;

	return find(oKey, iHash);
	}

	/**
	  @brief Find element in hash
	  @param oKey - key to find
	  @param iHash - hash
	  @return Iterator, piointed to element of end() if key not found
	*/
	iterator find(const TKey & oKey, TokenHash_t iHash);

	/**
	  @brief Clear hash without freeing memory
	*/
	void clear();

private:

	/**
	  @brief Decrease number of references and destroy hash if need
	*/
	void Destroy();

	/**
	  @brief Auto-expand hash
	*/
	void Unshare();

	/**
	  @brief Auto-expand hash
	*/
	INT_32 Expand();
};

} // namespace FTSS

#include <Hash.tcc>

#endif // _HASH_HPP__
// End.
